#ifndef _MUTABLE_ARRAY_HPP_
#define _MUTABLE_ARRAY_HPP_
#include "MutableContainer.hpp"

template<typename E>
class MutableArray : public MutableContainer<E>
{
private:
    E * array;//数组
    int len;  //数量

public:
    MutableArray();
    /* 在末尾添加元素 */
    void add(E ele)override;
    /* 在指定下标添加一个元素 */
    void add(int index, E ele)override;
    /* 按照下标删除元素 */
    E remove(int index)override;
    /* 按照元素进行删除 */
    bool removeElement(E ele)override;
    /* 清空容器 */
    void clear()override;
    /* 通过下标修改元素 */
    E set (int index, E ele)override;
    /* 通过下标获取元素 */
    E get(int index)override;
    /* 排序 */
    void sort()override;
    /* 查找元素出现的下标 */
    int index(E ele)override;
    /* 将容器中的元素拼接成字符串 */
    string str()override;    
    /* 获取元素个数 */
    int length()override;

    ~MutableArray() override;
};

template <typename E>
inline MutableArray<E>::MutableArray()
{
    array = new E[0];
    len = 0;
}

template <typename E>
inline int MutableArray<E>::length()
{
    return len;
}

/* 在末尾添加元素 */
template <typename E>
inline void MutableArray<E>::add(E ele)
{
    /* 添加的思想:创建一个新的数组，新数组的长度是原来数组的长度+1，再将原数组元素拷贝到新数组 */
    E * tmp = new E[len + 1];
    /* 拷贝原数组元素 */
    for(int idx = 0; idx < len; idx++)
    {
        tmp[idx] = array[idx];
    }
    /* 新增元素 */
    tmp[len] = ele;
    len++;
    /* 释放原数组空间 */
    delete array;
    /* 指向新空间 */
    array = tmp;
}
/* 在指定下标添加一个元素 */
template <typename E>
inline void MutableArray<E>::add(int index, E ele)
{
    E * tmp = new E[len + 1];
    /* 拷贝原数组元素 */
    for(int idx = 0, jdx = 0; idx < len; idx++)
    {   
        if(idx == index)
        {
            /* 将index下标空着留给新元素 */
            continue;
        }
        tmp[idx] = array[jdx++];
    }

    tmp[index] = ele;
    delete []array;
    array = tmp;
    len++;
}
/* 按照下标删除元素 */
template <typename E>
inline E MutableArray<E>::remove(int index)
{   
    /* 备份被删元素用于返回 */
    E ele = array[index];
    E* tmp = new E[len-1];
    for(int idx = 0, jdx = 0; idx < len; idx++)
    {
        if(idx == index)
        {
            continue;
        }
        tmp[jdx++] = array[idx];
    }
    delete []array;
    array = tmp;
    len--;
    return ele;
}
/* 按照元素进行删除 */
template <typename E>
inline bool MutableArray<E>::removeElement(E ele)
{
    int pos = MutableArray<E>::index(ele);
    if(pos != -1)
    {
        MutableArray<E>::remove(pos);
        return true;
    }
    return false;
}
/* 清空容器 */
template <typename E>
inline void MutableArray<E>::clear()
{
    if(array != nullptr)
    {
        delete []array;
        array = nullptr;
        len = 0;
    }
}
/* 通过下标修改元素 */
template <typename E>
inline E MutableArray<E>::set (int index, E ele)
{
    E tmp = array[index];
    array[index] = ele;
    return tmp;
}
/* 通过下标获取元素 */
template <typename E>
inline E MutableArray<E>::get(int index)
{
    return array[index];
}
/* 排序 */
template <typename E>
inline void MutableArray<E>::sort()
{
    for(int idx = 0; idx < len - 1; idx++)
    {
        int min = idx;
        for(int jdx = idx + 1; jdx < len; jdx++)
        {
            if(array[jdx] < array[min])
            {
                min = jdx;
            }
        }
        E tmp = array[idx];
        array[idx] = array[min];
        array[min] = tmp;
    }
}
/* 通过元素获取下标 */
template <typename E>
inline int MutableArray<E>::index(E ele)
{
    for(int idx = 0; idx < len; idx++)
    {
        if(array[idx] == ele)
        {
            return idx;
        }
    }
    return -1;
}
/* 将容器中的元素拼接成字符串 */
template <typename E>
inline string MutableArray<E>::str()
{
    if(len == 0)
    {
        return "[]";
    }
    /* 创建一个ostringstream的对象，用来拼接元素 */
    ostringstream oss;
    oss << "[";
    for(int i = 0; i < len - 1; i++)
    {
        oss << array[i] << ",";
    }
    oss << array[len - 1] << "]";

    return oss.str();
}   

/* 析构函数 */
template <typename E>
inline MutableArray<E>::~MutableArray()
{
    if(array != nullptr)
    {
        delete []array;
        array = nullptr;
    }
}

#endif